package org.egrit.util;

import java.awt.Point;
import java.util.List;

import com.google.common.base.Optional;
import com.google.common.collect.Lists;
import com.vividsolutions.jts.geom.Geometry;
import com.vividsolutions.jts.geom.Polygon;
import com.vividsolutions.jts.operation.union.UnaryUnionOp;

import org.egrit.GridGeometryIterator;
import org.egrit.GridUtils;
import org.egrit.IGrid;
import org.egrit.IGridBounds;

import org.jaitools.numeric.CompareOp;

/**
 * Used to build the bounding polygon of a connected region for a given grid.
 * A connected region is one in which all cells have the same value and any two
 * cells are linked by a path consisting exclusively of orthogonal connections.
 *
 * @author michael
 */
public class ConnectedRegionBuilder {
    
    private static final double TOL = 1.0e-8d;

    /**
     * Builds a connected region within an input grid. If successful, the
     * created region will:
     * 
     * <ol type="1">
     * <li> include the cell at {@code focalPos}
     * 
     * <li> contain only cells having the same value as the {@code focalPos} cell
     * 
     * <li> contains only cells which can be reached from any cell in the region
     *     via a path formed exclusively of orthogonal moves
     * </ol>
     * 
     * If a region meeting these conditions cannot be created, an empty {@linkplain Optional}
     * object is returned. 
     *
     * @param grid the input grid
     * @param initialBoundary the initial (largest possible) region boundary
     * @param focalPos position of a grid cell which must be included in the region
     * 
     * @return if successful, an {@linkplain Optional} object containing the region 
     *     boundary; otherwise an empty object
     * 
     * @throws IllegalArgumentException if any of the arguments are null
     */
    public static Optional<Polygon> build(IGrid grid,
            Polygon initialBoundary,
            Point focalPos) {

        grid.lock();
        try {
            Args.notNull(
                    "grid", grid,
                    "initialBoundary", initialBoundary,
                    "focalPos", focalPos);
            /*
             * If the initial boundary is empty there is no region to create.
             */
            if (initialBoundary.isEmpty()) {
                return Optional.absent();
            }
            
            /*
             * If the focal position is outside the bounds of the input grid
             * there is no region to create.
             */
            final IGridBounds inputGridBounds = grid.getGridBounds();
            if (!inputGridBounds.containsCell(focalPos)) {
                return Optional.absent();
            }
            
            /**
             * If the focal grid cell position is not in the initial boundary there
             * is not region to create.
             */
            if (!GridUtils.gridPosInPolygon(focalPos, initialBoundary)) {
                return Optional.absent();
            }
            
            /*
             * Get the value of the focal position cell. Region value 
             * comparisons will be done using double precision.
             */
            final double dRegionValue = grid.getGridValue(focalPos).doubleValue();
            
            /*
             * If the cell at focalPos has some value other than regionalValue there is
             * no region to create
             */
            if ( !CompareOp.aequal(grid.getGridValue(focalPos).doubleValue(), dRegionValue, TOL) ) {
                return Optional.absent();
            }
            
            /*
             * Trim the initial boundary if it extends beyond the input grid
             */
            Geometry trimmedGeom = GridUtils.trimPolygon(initialBoundary, grid.getGridBounds());
            if (trimmedGeom.isEmpty()) {
                // initial boundary was outside the bounds of the input grid
                return Optional.absent();
            }
            
            GridGeometryIterator iter = new GridGeometryIterator(trimmedGeom);

            /*
             * Remove any cells from the region which have another value
             * (working with double values)
             */
            List<Polygon> removeCells = Lists.newArrayList();
            
            do {
                Point pos = iter.getPos();
                if (Math.abs(grid.getGridValue(pos).doubleValue() - dRegionValue) > TOL) {
                    removeCells.add(GridUtils.createCellPolygon(pos));
                }
            } while (iter.next());

            Geometry valueSubsetGeom;
            if (removeCells.isEmpty()) {
                valueSubsetGeom = trimmedGeom;
                
            } else {
                Geometry union = UnaryUnionOp.union(removeCells);
                valueSubsetGeom = trimmedGeom.difference(union);
            }
            
            /*
             * Sanity check:
             * The subset geometry should never be empty - it should
             * at least contain the focal pos cell
             */
            if (valueSubsetGeom.isEmpty()) {
                throw new IllegalStateException("Empty geometry while creating region.");
            }
            
            Polygon finalBoundary = null;
            final int numParts = valueSubsetGeom.getNumGeometries();
            
            if (numParts == 1) {
                finalBoundary = (Polygon) valueSubsetGeom;
                
            } else {
                /*
                 * Find the part which contains the focal position
                 */
                for (int i = 0; i < numParts; i++) {
                    Polygon part = (Polygon) valueSubsetGeom.getGeometryN(i);
                    if (GridUtils.gridPosInPolygon(focalPos, part)) {
                        finalBoundary = part;
                        break;
                    }
                }
            }

            if (finalBoundary == null) {
                throw new IllegalStateException("Failed to find polygon containing focal position");
            }
            
            return Optional.of(finalBoundary);

        } finally {
            grid.unlock();
        }
    }
}
